1. Field of the Invention
The present invention generally relates to geometric modeling in computer graphics (CG). Specifically, the present invention relates to a method, system and program product for re-meshing of a three-dimensional input model using progressive implicit approximating levels.
2. Related Art
Geometric modeling is a fundamental problem in computer graphics (CG). Typical CG pipelines favor triangles as the most commonly used geometric primitives since triangle meshes are easy to model, render, and animate. Recently, quadrilateral-based subdivision surfaces have been proven to offer advantages over triangle meshes for modeling and editing of complex shapes.
The conversion of a given triangle mesh into a quad-based semi-regular mesh suitable for generating a subdivision surface requires re-meshing. Automatically generating an all-quads manifold surface with a small number of quads so as to keep the complexity of subdivided meshes derived from it low, yet sufficient to capture input features, is a challenging problem. A given triangulated model might have millions of triangles that capture all surface details. A multi-resolution subdivision surface that describes the same model will have a much coarser base mesh and a sequence of detail levels that describe progressively better approximations of the input surface through offset or detail vectors with respect to the positions obtained by subdivision of control meshes on coarser levels. One challenge is to find a suitable coarse mesh, which does not have too many faces, yet optimizes the placement of these faces with respect to the input geometry so that the input can be approximated well with only few and small perturbations (i.e., offsets or details).
A good quality base mesh captures the important geometric properties of the original mesh, such as topology, symmetry and sharp features. Some efforts have been made in this field. For example, one method to achieve this goal is to first decimate then re-arrange the connectivity of the input triangle mesh to produce a quad mesh. A sequence of local re-meshing operations such as triangle pairings makes this scheme fail to preserve global properties such as symmetry of the original shape and the output heavily depends on the original connectivity. Other recent works make use of vector fields defined on the mesh surface to guide the re-meshing operations. Such methods lead to meshes that better capture symmetries, but they result in relatively fine meshes with many elements (the number of elements will be proportional to the size of the smallest feature of the object). Although this new idea offers the ability to re-mesh without dependency on the input connectivity, this strategy remains a surface-based approach that limits the manipulation over the 2D domain of the surface.